\section{Faktorizácia}

\subsection{Náhodné zobrazenia}
Ešte predtým, ako sa vrhneme na algoritmy pre faktorizáciu, zhrnieme
si niekoľko užitočných tvrdení, ktoré budeme neskôr využívať. Jedná sa
hlavne o vlastnosti náhodného zobrazenia.

Majme náhodné zobrazenie $f:X \rightarrow X$, kde $|X| = n$.
Budeme uvažovať postupnosť $x_0 = s,\ x_1=f(s)=f(x_0),\ x_2 =
f(f(s))=f(x_1),\ \dots,\ x_{i+1} = f(x_{i})$ pre nejaké začiatočné $s$.
Keďže obor hodnôt je konečný, najviac po $n$ krokoch sa nám nejaké
číslo zopakuje a dostaneme cyklus. Vo všeobecnosti môžeme postupnosť
rozdeliť na začiatočný ``chvost'' dĺžky $\lambda$ a cyklus dĺžky
$\mu$, ako na obrázku \ref{fig:cyclelen}.

\begin{figure}[h!]
    \centering
    \includegraphics[scale=0.9]{img/03/cyclelen.1.mps}
    \caption{Chvost a telo cyklu pri náhodnom zobrazení}
    \label{fig:cyclelen}
\end{figure}

\noindent
Základom pre ďalšiu analýzu bude nasledujúce tvrdenie:

\begin{lema}
    Nech $f:X\rightarrow X, |X|=n$ je náhodné zobrazenie.
    Potom pre $n\rightarrow \infty$ platí
    $\lambda \sim \sqrt{\pi n/8}$ a 
    $\mu \sim \sqrt{\pi n/8}$.
\end{lema}
\begin{dokaz}
    Dôkaz nebudeme robiť, nakoľko vyžaduje netriviálne znalosti
    z generujúcich funkcií. Čitateľ ho môže nájsť napríklad v článku
    \cite{randommap}.
\end{dokaz}

Za pomoci predchádzajúceho tvrdenia môžeme hľadať ``kolízie'' v
postupnosti v očakávanom čase $\Theta(\sqrt{n})$.
Jednoduchým riešením je napríklad použiť hashovanie na každý prvok
postupnosti $x_i$. Praktický problém, ku ktorému ale narážame je
pamäť, ktorá by musela byť $\Theta(\sqrt{n})$, čo je v dnešnej dobe
limitujúci faktor. Existujú však aj metódy na hľadanie cyklov,
ktoré používajú konštantnú pamäť.

\subsubsection{Metódy na hľadanie cyklov}

Začneme Floydovou metódou, ktorá sa niekedy aj označuje metódou dvoch
bežcov. Pracuje na veľmi jednoduchom princípe -- predstavme si, že máme
2 bežce -- ukazovatele na prvky postupnosti. Ak jedným bežcom budeme
pohybovať rýchlejšie ako druhým a oba tieto prvky ležia v cykle, po
istom čase (najneskôr celý prechod cyklu) jeden z ukazovateľov dobehne
ten prvý. Formálne, metóda porovnáva nasledujúce dvojice prvkov:
$(x_1,x_2),\ (x_2,x_4),\ (x_3,x_6),\ (x_4,x_8),\ \dots$.
Jej funkčnosť dokážeme nasledovne: Predpokladajme, že v aktuálnom
kroku algoritmu máme prvky $x_i, x_{j=2i}$. Ďalej redpokladajme,
že oba tieto prvky ležia v cykle, ktorého dĺžka je $\lambda$.
Ak by platilo $i \equiv j \pmod{\lambda}$, tak nutne platí $x_i = x_j$.
Uvažujme teda, že rovnosť nenastáva. V tom prípade ale platí 
$j-i \equiv i \pmod{\lambda}$. Na začiatku je táto hodnota 0 
a každým krokom algoritmu vzrastie o 1. Čiže,
najneskôr o $\lambda$ krokov bude $j-i \equiv 0 \pmod{\lambda}$.
Preto môžeme časovú zložitosť algoritmu ohraničiť ako $O(\mu+\lambda)$.

\begin{algorithm}
    \caption{Floydov algoritmus na hľadanie cyklov}
    \label{algo:floyd}
    $x1 \assign f(s)$\;
    $x2 \assign f(f(s))$\;
    \While{$x1 \ne x2$}{
        $x1 \assign f(x1)$\;
        $x2 \assign f(f(x2))$\;
    }
    output $\assign$ prvok cyklu je $x1$\;
\end{algorithm}

\medskip
Ďalšou metódou je Brentova metóda detekcie cyklov. Má rovnakú
asymptotickú časovú zložitosť ako Floydova, v praxi však používa menej
výpočtov funkcie $f$ a preto je zväčša preferovaná.
Metóda funguje v akýchsi blokoch mocniny dvojky.
Porovnáva hodnotu $x_{2^i}$ postupne s nasledujúcimi číslami
$x_{2^i+k}$, až dosiahneme ďalšiu mocninu dvojky, vtedy začneme ďalším
blokom. Algoritmus skončí v okamihu, keď je dĺžka aktuálneho bloku
(mocnina dvojky) väčšia ako dĺžka cyklu a už sme do cyklu vošli.
Preto je čas Brentovej metódy $O(\lambda + \mu)$.
Graficky je to naznačené na obrázku \ref{fig:brent} a príslušný
algoritmus je \ref{algo:brent}.

\begin{figure}[h!]
    \centering
    \includegraphics{img/03/brent.1.mps}
    \caption{Brentova metóda na hľadanie cyklov}
    \label{fig:brent}
\end{figure}

\begin{algorithm}
    \caption{Brentov algoritmus}
    \label{algo:brent}
    $x1 \assign f(s)$\;
    $x2 \assign f(f(s))$\;
    $i \assign 2$\;
    \While{$x1 \ne x2$}{
        \If{$i$ je 2. mocnina}{
            $x1 \assign x2$\;
        }
        $x2 \assign f(x2)$\;
        $i \assign i+1$\;
    }
    output $\assign$ prvok cyklu je $x1$\;
\end{algorithm}

\subsection{Pollardova metóda na faktorizáciu}
\todo{Pollard}
\todo{Dixon}
\todo{Quadratic sieve}
